/*
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0开头。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
package LC0002;

// 链表
public class LC0002 {

    class ListNode {    // 定义一个链表结点类
        int val;    // 结点存储的值
        ListNode next;  // 指向下一个结点的指针
        ListNode(int x) { val = x; }    // 构造函数
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummyHead = new ListNode(0);   // TODO 第一个结点为0?

        ListNode p = l1, q = l2;
        // p, q指向两个参数链表的头
        ListNode curr = dummyHead;
        // curr指向新链表的头

        int carry = 0;  // 存储向下一位进位的值

        while (p != null || q != null) {    // 当指针走到两个参数链表之一的结尾（null），就结束   // TODO 链表结尾是null? 链表头呢?
            int x = (p != null) ? p.val : 0;    // 三元操作符
            int y = (q != null) ? q.val : 0;    // 指向的结点不为空，取出结点的值（val）和carry相加；// TODO 如果是空，会怎么样?
            int sum = carry + x + y;    // 这样carry可以被新的十位数覆盖了
            carry = sum / 10;   // carry存储相加的十位数 // TODO carry最多是1?
            curr.next = new ListNode(sum % 10); // 相加的个位数放入新链表的结点   // TODO 所以新链表的头为0??
            curr = curr.next; // 先给下一个结点赋值，再把新链表的指针指向下一个结点
            if (p != null) p = p.next;  // 当前结点不为空，指向下一个结点
            if (q != null) q = q.next;  // 这是考虑到其中一个链表可能为空的情况   // TODO 如果一个空的结点，让它指向下一个结点会怎么样?
        }

        // 如果其中一个链表计算完，还有进位，把值直接放入新链表的下一个结点； // 也就是新链表可能比参数链表更长一点
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }

        return dummyHead.next;
        // TODO 为什么返回值是next？
            // 因为第一个是空的
    }

    public static void main(String[] args) {

    }
}
